#include<iostream>
#include<vector>
#include<time.h>
#include<sys/timeb.h>
#include<Windows.h>
#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
//#include<RandomNumber.h> 
using namespace std;
class RandomNumber
{
	public:
		RandomNumber(){
			srand(time(0));
		}
		unsigned random(int,int);
	private:
		
};
unsigned RandomNumber::random(int begin=0,int end=1)
{
	return rand()%(end-begin+1)+begin; 
}
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
		 int max = INT_MIN;
        int numsSize = int(nums.size());
        for (int i = 0; i < numsSize; i++)
        {
            int sum = 0;
            for (int j = i; j < numsSize; j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }

        return max;
    }

};
int main()
{
	 DWORD start1,end1;
	 start1 = GetTickCount();
	 srand((unsigned)time(0));
	  
	/*int b[]={1,2,3,1,2,3};    //情况一:输入的元素全部为正整数 
	vector<int> a(b,b + 6); */ 
/*	int b[]={-1,-2,-3,-1,-2,-3};    //情况二:输入的元素全部为负整数
	vector<int> a(b,b + 6); */
/*	int b[]={-1,2,3,1,-2,-3};    //情况三:输入的元素包含正整数与负整数
	vector<int> a(b,b + 6); */
/*	int b[]={};    				//情况四:输入的数据为空
	vector<int> a(b,b + 0); */
/*	vector<int> a;				//	情况五:输入的数据量极大
	
	for(int i = 0;i < 100000;i++)
	{
		a.push_back(i);
	} */
	vector<int> a;				// 情况六:随机数
	RandomNumber number;
	for(int i = 0;i < 10000;i++)
	{	
		int b;
		b = number.random(-1000,1000);
		//cout<<b<<" ";
		a.push_back(b);
	}
	cout<<endl; 
	

	Solution c;
	int d;
	d = c.maxSubArray(a);
	cout<<d<<endl;
	
	end1 = GetTickCount();
	cout<<"time(ms) "<<end1 - start1<<endl;
	
	return 0;	
} 
